package homework;

import java.util.Scanner;

public class Homework8_20 {
    static int count;
    public static void main(String[] args) {

//        System.out.println(fibNonRecursion(48));
//        System.out.println(factorial(5));
//        System.out.println(addRecursion(10));
//        print(1892);
//        System.out.println();
//        System.out.println(sum(1234));
//        System.out.println(fib(10));
        int n = 3;
        hanoiTower(n,'A','B','C');
        System.out.println("总共移动了" + count + "次");

    }

    //迭代求斐波那契数列的第N项
//    public static int fibNonRecursion(int num){
//        int n2 = 1;
//        int n1 = 1;
//        int n = 0;
//        for (int i = 3; i <= num; i++) {
//            n = n2 + n1;
//            n2 = n1;
//            n1 = n;
//        }
//        return n;
//    }

    //递归求N的阶乘
//    public static int factorial(int n){
//        if(n == 1 || n == 2){
//            return n;
//        }
//        return n * factorial(n-1);
//    }

    //递归求和
//    public static int addRecursion(int n){
//        if(n == 1){
//            return n;
//        }
//        return n + addRecursion(n-1);
//    }

    //递归打印数字的每一位
//    public static void print(int num){
//        if(num < 10){
//            System.out.print(num + " ");
//            return;
//        }
//        print(num / 10);
//        System.out.print(num % 10 + " ");
//    }

    //递归返回数字之和
//    public static int sum(int num){
//        if(num < 10){
//            return num;
//        }
//        return num % 10 + sum(num / 10);
//    }

    //递归求斐波那契数列第N项
//    public static int fib(int n){
//        if(n == 1 || n == 2){
//            return 1;
//        }
//        return fib(n-1) + fib(n-2);
//    }

    //递归求汉诺塔问题
    public static void hanoiTower(int nDisks,char A,char B,char C){
        if(nDisks == 1){
            move(1,A,C);
            return;
        }
        hanoiTower(nDisks - 1,A,C,B);
        move(nDisks,A,C);
        hanoiTower(nDisks - 1,B,A,C);
    }
    public static void move(int nDisks,char sourceTower,char distTower){
        System.out.println("正在将编号为" + nDisks + "的盘子从" + sourceTower + "->" + distTower);
        count ++;
    }
}
